//https://leetcode.cn/problems/search-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked
//好题目！！
#include <vector>
#include <stack>
#include <list>
#include <map>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int min_index=minNumberInRotateArray(nums);
        int res1 = binarySearch(nums,0,min_index,target);
        if(!(res1==min_index || nums[res1]!=target) ){
           return res1;
        } 
        int res2 = binarySearch(nums,min_index,nums.size(),target);
        if(!(res2==nums.size() || nums[res2]!=target) ){
           return res2;
        } 
        return -1;
    }

    int binarySearch(vector<int>& data, int left,int right,int k){
        // 左右边界
        int l = left, r = right;
        while(l < r){
            // 二分求中点
            int m = l+(r-l)/2;
            if(data[m] >= k)
                r = m;
            else
                l = m+1;
        }
        // 返回左边界
        return l;
    }

    int minNumberInRotateArray(vector<int> rotateArray) {
        int left = 0;
        int right = rotateArray.size() - 1;
        while(left < right){
            int mid = (left + right) / 2;
            //最小的数字在mid右边
            if(rotateArray[mid] > rotateArray[right])
                left = mid + 1;
            //无法判断，一个一个试
            else if(rotateArray[mid] == rotateArray[right])
                right--;
            //最小数字要么是mid要么在mid左边
            else
                right = mid;
        }
        return left;
    }
};